package com.leetcode.q633;

import java.util.ArrayList;
import java.util.List;

/**
 * <p> description: desc</p>
 *
 * @author tanzc
 * @date 2022/3/30
 **/
public class JudgeSquareSum {
    public boolean judgeSquareSum(int c) {
        boolean flug = false;
        List<Double> powList = new ArrayList<>();
        double sqrt = Math.sqrt(c);
        for (int i = 0; i <= sqrt; i++) {
            powList.add(Math.pow(i, 2));
        }
        int left = 0, right = powList.size() - 1;
        if (powList.get(0) == c || powList.get(right) == c) {
            flug = true;
        }
        double cc;
        while (left <= right) {
            cc = powList.get(left) + powList.get(right);
            if (cc == c) {
                flug = true;
                break;
            } else if (cc < c) {
                left++;
            } else {
                right--;
            }
        }
        return flug;
    }

    public boolean judgeSquareSum2(int c) {
        double left = 0, right = Math.floor(Math.sqrt(c));
        double cc;
        while (left <= right) {
            cc = Math.pow(left, 2) + Math.pow(right, 2);
            if (cc == c) {
                return true;
            } else if (cc < c) {
                left++;
            } else {
                right--;
            }
        }
        return false;
    }

    public boolean judgeSquareSum3(int c) {
        for (long a = 0; a * a <= c; a++) {
            double b = Math.sqrt(c - a * a);
            if (b == (int) b) {
                return true;
            }
        }
        return false;
    }
}
